package main

import "fmt"

func main() {

	fmt.Println(bag([]int{1, 3, 4}, []int{15, 20, 30}, 4))
}

func bag(weight, value []int, bagWeight int) int {
	var dp [][]int
	for i := 0; i < len(weight); i++ {
		dp = append(dp, make([]int, bagWeight+1))
	}

	for i := weight[0]; i <= len(weight); i++ {
		dp[0][i] = value[0]
	}

	for i := 1; i < len(weight); i++ {
		for j := 1; j <= bagWeight; j++ {
			if j < weight[i] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = Max3(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
			}
		}
	}

	return dp[len(dp)-1][len(dp[0])-1]
}

func Max3(a, b int) int {
	if a < b {
		return b
	}
	return a
}
